package com.ryujung.dfs_backtracking;

import java.util.*;

class Solution47 {
    /**
     * 和46很像，但是多了nums中数字重复的情况，
     * 所以在回溯中要进行去重
     * <p>
     * 时间复杂度：O(n×n!)，其中 n 为序列的长度。
     * 算法的复杂度首先受 backtrack 的调用次数制约，backtrack 的调用次数为 ∑k=1nP(n,k)∑k=1n​P(n,k) 次，其中 P(n,k)=n!(n−k)!=n(n−1)…(n−k+1)P(n,k)=(n−k)!n!​=n(n−1)…(n−k+1)，该式被称作 n 的 k - 排列，或者部分排列。
     * 而 ∑k=1nP(n,k)=n!+n!1!+n!2!+n!3!+…+n!(n−1)!<2n!+n!2+n!22+n!2n−2<3n!∑k=1n​P(n,k)=n!+1!n!​+2!n!​+3!n!​+…+(n−1)!n!​<2n!+2n!​+22n!​+2n−2n!​<3n!
     * 这说明 backtrackbacktrack 的调用次数是 O(n!)O(n!) 的。
     * 而对于 backtrackbacktrack 调用的每个叶结点（最坏情况下没有重复数字共 n!n! 个），我们需要将当前答案使用 O(n) 的时间复制到答案数组中，相乘得时间复杂度为 O(n×n!)。
     * 因此时间复杂度为 O(n×n!)。
     *
     * 空间复杂度：O(n)。
     * 我们需要 O(n) 的标记数组，同时在递归的时候栈深度会达到 O(n)，因此总空间复杂度为 O(n+n)=O(2n)=O(n)。
     * <p>
     * 方式一：在dfs中使用数组对已经遍历的数字进行记录，并在后序的遍历中跳过相同值的nums[i]
     * 方式二：预先将整个数组进行排序，在循环中判断当前值nums[i]是否和nums[i-1]相同，相同则跳过
     * 方式二的判断是否要跳过的部分比较难理解，1.已经使用过的需要跳过。2.没有使用过但是重复，上一个重复值还没有使用过，
     * <p>
     * 解答成功:
     * 执行耗时:1 ms,击败了99.49% 的Java用户
     * 内存消耗:42 MB,击败了87.13% 的Java用户
     */
    public List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> ans = new ArrayDeque<>();
        boolean[] isHasUsedArr = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, 0, isHasUsedArr, ans, res);
        return res;
    }

    private void dfs(int[] nums, int index, boolean[] isHasUsedArr, Deque<Integer> ans, List<List<Integer>> res) {
        if (index == nums.length) {
            res.add(new ArrayList<>(ans));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 使用过的跳过，重复且上一个值没有被使用过的跳过
            boolean isDuplicated = i > 0 && nums[i] == nums[i - 1];
            if (isHasUsedArr[i] || (isDuplicated && !isHasUsedArr[i - 1])) {
                continue;
            }
            ans.addLast(nums[i]);
            isHasUsedArr[i] = true;
            dfs(nums, i + 1, isHasUsedArr, ans, res);
            isHasUsedArr[i] = false;
            ans.removeLast();
        }
    }

    /**
     * 和46很像，但是多了nums中数字重复的情况，
     * 所以在回溯中要进行去重
     * <p>
     * 方式一：在dfs中使用数组对已经遍历的数字进行记录，并在后序的遍历中跳过相同值的nums[i]
     * 方式二：预先将整个数组进行排序，在循环中判断当前值nums[i]是否和nums[i-1]相同，相同则跳过
     * <p>
     * 解答成功:
     * 执行耗时:1 ms,击败了99.49% 的Java用户
     * 内存消耗:42 MB,击败了83.44% 的Java用户
     */
    public List<List<Integer>> permuteUnique1(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> ans = new ArrayDeque<>();
        boolean[] isHasUsedArr = new boolean[nums.length];
        dfs1(nums, 0, isHasUsedArr, ans, res);
        return res;
    }

    private void dfs1(int[] nums, int index, boolean[] isHasUsedArr, Deque<Integer> ans, List<List<Integer>> res) {
        if (index == nums.length + 1) {
            return;
        }
        if (ans.size() == nums.length) {
            res.add(new ArrayList<>(ans));
        }
        // nums[i]:-10~10
        boolean[] isHasIterateArr = new boolean[21];
        for (int i = 0; i < nums.length; i++) {
            if (!isHasUsedArr[i] && !isHasIterateArr[nums[i] + 10]) {
                ans.addLast(nums[i]);
                isHasUsedArr[i] = true;
                isHasIterateArr[nums[i] + 10] = true;
                dfs1(nums, i + 1, isHasUsedArr, ans, res);
                isHasUsedArr[i] = false;
                ans.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Solution47 s = new Solution47();
        System.out.println(s.permuteUnique1(new int[]{1, 2, 2}));
        System.out.println(s.permuteUnique2(new int[]{2, 2, 2}));
    }
}